package com.agile.leetcode.tree.isSymmetric;


import java.util.Deque;
import java.util.LinkedList;

/**
 * 对称二叉树
 *
 * @Author:ChenZhangKun
 * @Date: 2021/4/17 19:06
 */
public class IsSymmetric {
    public boolean isSymmetric(TreeNode root) {
        return function_1(root, root);
    }

    /**
     * 递归的方式
     * 如果同时满足下面的条件，两个树互为镜像:
     * 1 它们的两个根结点具有相同的值
     * 2 每个树的右子树都与另一个树的左子树镜像对称
     *
     * @param t1
     * @param t2
     * @return
     */
    public boolean function_1(TreeNode t1, TreeNode t2) {
        // 全部为空时，则为true
        if (t1 == null && t2 == null) {
            return true;
        }
        // 有一个为null则返回false
        if (t1 == null || t2 == null) {
            return false;
        }
        return t1.val == t2.val && function_1(t1.left, t2.right) && function_1(t1.right, t2.left);
    }

    /**
     * 迭代的方式
     * 首先我们引入一个队列，这是把递归程序改写成迭代程序的常用方法。
     * 初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），
     * 然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。
     *
     * @param t1
     * @param t2
     * @return
     */
    public boolean function_2(TreeNode t1, TreeNode t2) {
        // 创建队列
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(t1);
        deque.offer(t2);
        // 循环
        while (!deque.isEmpty()) {
            // 取出
            t1 = deque.poll();
            t2 = deque.poll();
            if (t1 == null && t2 == null) {
                continue;
            }
            if (t1 == null || t2 == null || (t1.val != t2.val)) {
                return false;
            }
            deque.offer(t1.left);
            deque.offer(t1.right);
            deque.offer(t2.right);
            deque.offer(t2.left);
        }
        return true;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
